'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-10-17 09:59:26
'''
'''
Problem
=======

考虑某一股票的价格P，每过一段时间我们能获得一对数(t, Pt)，分别为当前的时间戳t和当前该股票的价格Pt，需要计算该股票在[t-W, t]时间段内的平均价格，
其中W是事先给定的窗口大小，单位和t相同。

请编写程序来实现这个计算过程。接口参见以下Interface节。

算法需要满足以下要求：

1. 相邻数据点之间的间隔不固定，可能有较大变化，在计算的时候应考虑数据间隔变化极端的情况下的鲁棒性;
2. 计算的平均价格应能较好反映股票价格在窗口时间内的“平均水平”
3. 假设在相邻两次数据到达期间内，股票的真实价格都等于前一次数据的价格
4. 所谓平均水平指的是股票价格在窗口内的简单移动平均（SMA）而不是指数移动平均（EMA）
5. 可用的内存大小是有限的，为O(num_bin)规模，当窗口内到达的数据量超过可用的存储空间时，**应做一定的取舍，既不突破内存限制，又尽可能保证结果的精确性**（只是简单地把尾部数据删除是不行的）
6. 实现以下MovingAverage接口
7. 尽量使用性能较优的算法和实现方法
8. 尽量不要使用第三方库

编程语言: Python / C++

Note
====

num_bin: 使用的内存大小应为O(num_bin)级别
window：移动平均的窗口长度

timestamp是时间戳，浮点数，数据间隔不固定，可能一秒来几十个数据，也可能几小时来一个数据


Interface
=========

（以python为例）
class MovingAverage:
    def __init__(self, num_bin: int, window: float):
        pass

    def Get(self) -> float:
        "返回当前计算的平均值"
        raise NotImplementedError
        
    def Update(self, timestamp: float, value: float):
        "新数据到达，更新状态"
        raise NotImplementedError

每次数据到达时，会依次调用Update和Get方法

'''

class MovingAverage:
    def __init__(self, num_bin: int, window: float):
        #windows, used_bin, tot_p, num_bin, ext_num, 以及update时要来的两个float量所占字节
        import time
        tot = 8 +    8       + 8   + 8      +8   + 16
        self.num_bin = num_bin - tot #所能存储的字节上限
        self.window = window #存储的时间窗口。
        self.used_bin =  0 #用以存储已用空间。
        self.prices = [] #存储满足条件的股票价格。
        self.timestamps = [] #存储满足条件的时间戳，每个时间戳与同脚标price一一对应.
        pass

    def Get(self) -> float:
        #为了较好的反应平均水平，采用**时间间隔加权平均**的方法求简单平均值。
        # print('========len of prices is ', len(self.prices), 'len of timestamps is ', len(self.timestamps))
        total = 0
        current = time.time()
        start = current-self.window
        i=0
        while i<len(self.timestamps):
            if self.timestamps[i]>start:
                break
            i+=1
        i = i-1 if i>0 else 0
        self.prices = self.prices[i:]
        self.timestamps = self.timestamps[i:]
        self.used_bin -= 16*i if i>0 else 0
        last_time = self.timestamps[0]
        v_before = self.prices[0]
        for i, (t, v) in enumerate(zip(self.timestamps, self.prices)):
            if i==0:
                continue
            total += v_before*(t-last_time)
            v_before = v
            last_time = t
        total += (current-last_time)*v_before
        return total/self.window
        raise NotImplementedError
        
    def Update(self, timestamp: float, value: float):
        # "新数据到达，更新状态"
        # print('========len of prices is ', len(self.prices), 'len of timestamps is ', len(self.timestamps), 'used space is ', self.used_bin)
        # if self.timestamps:
        #     print('window is ', self.window, 'total gap is ', self.timestamps[-1]-self.timestamps[0])
        self.used_bin += 16
        self.prices.append(value)
        self.timestamps.append(timestamp)
        i = 0
        while i<len(self.timestamps):
            if self.timestamps[i]>timestamp-self.window:
                break
            i+=1
        i = i-1 if i>0 else 0
        # print('------updata-------', i)
        self.prices = self.prices[i:]
        self.timestamps = self.timestamps[i:]
        self.used_bin -= 16*i if i>0 else 0

        # 内存可能超过时，将内存可能超过的项以及后面一项结合起来算一个综合平均，作为窗口开始的新值，作为近似，能更加精确。
        if self.used_bin>=self.num_bin:
            # print(timestamp, len(self.timestamps), self.used_bin)
            total = (self.timestamps[1]-self.timestamps[0])*self.prices[0]+(self.timestamps[2]-self.timestamps[1])*self.prices[1]
            avg = total/(self.timestamps[2]-self.timestamps[0])
            self.prices.pop(0)
            self.timestamps.pop(1)
            self.prices[0]=avg
            self.used_bin -= 16
        return
        raise NotImplementedError

import time
if __name__ == "__main__":
    current = time.time()
    import numpy as np
    time_gap = np.random.uniform(high=1000, size=100)
    time_gap.sort()
    timestamps = [current-i for i in time_gap]
    timestamps.reverse()
    mavg = MovingAverage(1000, 100)
    prices = np.random.uniform(size=100)
    # print(timestamps)
    # print(prices)
    for t,p in zip(timestamps, prices):
        mavg.Update(t, p)
        print(mavg.Get())